#! /usr/bin/env python
# -*- coding: utf-8 -*-

# Copyright (c) Huoty, All rights reserved
# Author: Huoty <sudohuoty@163.com>
# CreateTime: 2020-06-08 23:09:32

class BHeap(object):
    """二叉堆（这里为一个大顶堆）"""

    def __init__(self):
        self._heap = []

    @property
    def _size(self):
        return len(self._heap)

    def is_empty(self):
        return not self._heap

    def perc_up(self, index):
        """节点上浮"""
        cur_pos = index
        while cur_pos > 0:
            parent = (cur_pos - 1) // 2  # 获取父节点位置
            item = self._heap[cur_pos]
            parent_item = self._heap[parent]
            # 与父节点比较，如果比父节点大，则上浮（即与父节点交换位置）
            if item <= parent_item:
                break

            self._heap[cur_pos], self._heap[parent] = self._heap[parent], self._heap[cur_pos]
            cur_pos = parent

    def add(self, data):
        """添加元素到堆"""
        self._heap.append(data)       # 先将元素插入到堆底
        self.perc_up(self._size - 1)  # 然后再将其不断上浮合适位置

    def get_max_child(self, index):
        """获取某个节点最大的子节点"""
        lchild = 2 * index + 1  # 左子节点
        rchild = 2 * index + 2  # 右子节点
        last_index = self._size - 1
        if lchild > last_index:
            raise Exception("位于 %s 的节点没有子节点" % index)
        elif rchild > last_index:
            # 如果没有右节点，就返回左节点
            return lchild
        else:
            # 返回所有子节点中值最大的节点的位置
            return lchild if self._heap[lchild] > self._heap[rchild] else rchild

    def perc_down(self, index):
        """节点下沉"""
        lchild = 2 * index + 1
        last_index = self._size - 1
        cur_pos = index
        while lchild <= last_index:
            max_child = self.get_max_child(cur_pos)
            if self._heap[cur_pos] >= self._heap[max_child]:
                break

            # 当子节点中有比父节点大的节点时，根节点下沉
            self._heap[cur_pos], self._heap[max_child] = self._heap[max_child], self._heap[cur_pos]
            cur_pos = max_child
            lchild = 2 * cur_pos + 1

    def pop(self):
        """弹出堆顶元素"""
        if self.is_empty():
            raise Exception("heap is empty")
        top_item = self._heap[0]
        self._heap[0] = self._heap.pop()
        self.perc_down(0)
        return top_item

    def build_from_sequence(self, sequence):
        """从一个序列构建堆

        在二叉堆中，从数组的中间位置往后的节点都是叶子节点
        利用这个特性，只需将中间位置往前的元素（非叶子节点）下沉
        便可以将一个无序的数组调整为二叉堆
        """
        self._heap = list(sequence)
        mid_index = (self._size - 1) // 2
        for index in range(mid_index, -1, -1):
            self.perc_down(index)
